package com.backpack;

public class HouseRobber0113_198 {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        //动态规划 01背包问题 （小偷不重复偷）
        //dp[i] 表示 偷到下标 i (含)家之前的所有，偷到的最大金额是 dp[i]  返回值 dp[nums.length]
        int[] dp = new int[nums.length];

        //初始化
        dp[0] = nums[0];
        dp[1] = Math.max(dp[0],nums[1]);

        // 递推公式：考虑偷 i（偷 i 的话，就只能将 i-2 考虑进去）   与   考虑不偷 i（不偷 i，也不一定就要偷 i-1，只是将 i-1 考虑进去 ） ，求最大
        // 递推公式：dp[j] = Math.max(dp[j-2]+nums[i]，dp[j-1]);
        //遍历顺序：先遍历物品（正序），再遍历背包（倒序，因为小偷不重复偷盗）;       可颠倒??
        for (int i = 1; i < nums.length; i++) {
            for (int j = nums.length-1; j >=2 ; j--) {
                dp[j] = Math.max(dp[j-2]+nums[j],dp[j-1]);
                System.out.println(dp[j]);
            }
            System.out.println("-----------");
        }


        //不用两层循环，以下思路简单点，不用考虑那么复杂，直接一趟遍历到最后就行得出dp[nums.length-1]即可。
//        for (int i = 2; i < nums.length; i++) {
//            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
//        }
        System.out.println("nums[]:" + dp[nums.length - 1]);
        return dp[nums.length-1];
    }

    public static void main(String[] args) {
        HouseRobber0113_198 test = new HouseRobber0113_198();
        test.rob(new int[]{2,7,9,3,1});
    }
}
